import java.util.Collection;
import java.util.Iterator;

/**
 * CS 1332 Extra Credit Homework
 * @author Jihoon Lee
 * This class implements HeapInterface<T> and extends Comparable<T>.
 * It uses an array to implement a heap data structure.
 * It starts putting elements from index 1. It makes the operation easier.
 */

public abstract class Heap<T extends Comparable<T>> implements HeapInterface<T> {

	public abstract int priority(T one, T two);

	/**
	 * This is the array containing your data. You MUST leave index 0 empty or
	 * your grade will be low. So start putting stuff at index 1, this will
	 * actually make the heap easier to implement.
	 */
	private T[] array;
	private int size;

	/**
	 * Initializes the array with a default capacity of 11, and initializes the
	 * size to 0.
	 */
	public Heap() {
		array = (T[]) new Comparable[11];
		size = 0;
	}

	/**
	 * Initializes the array with the given capacity, you do not need to do any
	 * checks on the capacity, it will be valid in our tests. and initialize the
	 * size to 0.
	 * 
	 * @param capacity
	 *            the starting capacity of the heap
	 */
	public Heap(int capacity) {
		array = (T[]) new Comparable[capacity];
		size = 0;
	}

	/**
	 * isEmpty() method.
	 * @return true if the heap is empty, 
	 * 		false if the heap has some elements
	 */
	
	public boolean isEmpty() {
		if(size == 0){
			return true;
		}
		else{
			return false;
		}
	}

	/**
	 * size() method.
	 * @return size number of elements in the heap.
	 */
	
	public int size() {
		return size;
	}

	/**
	 * getFirst() method.
	 * @return T first element in heap.
	 */
	
	public T getFirst() {
		if(isEmpty()){
			return null;
		}
		else{
			return array[1];
		}
	}

	/**
	 * remove() method.
	 * @return T first element that has been removed.
	 * This method removes first element in the heap and return it.
	 * It sets the first element of the heap to the last element
	 * then uses removeSwap() method to do the swap operation 
	 * for the heap structure.
	 */
	
	public T remove() {
		if(isEmpty()){
			return null;
		}
		
		T removed = array[1];
		array[1] = array[size];
		array[size] = null;
		size--;
		
		removeSwap(1);
		return removed;
	}
	
	/**
	 * removeSwap() method.
	 * @param index = 1, always the first element.
	 * This method performs a heapifying process using recursion.
	 */
	
	private void removeSwap(int index){
		T temp;
		//if the index we are looking for is bigger than 
		//the maximum index of the array just return.
		if(2*index + 1 > array.length - 1){ 
			return;
		}
		else{
			//null check first
			if(array[2*index]==null && array[2*index + 1]==null){
				return;
			}
			//since heap is a complete tree, 2*index + 1 position can be null.
			else if(array[2*index]!=null && array[2*index + 1]==null){
				//if swap operation is needed, swap.
				if(priority(array[index], array[2*index])<0){
					temp=array[index];
					array[index] = array[2*index];
					array[2*index] = temp;
				}
				else{
					return;
				}
			}
			else{ //When null check is not needed, recursively do the swap operation.
				if(priority(array[2*index + 1], array[2*index]) < 0){
					temp=array[index];
					array[index] = array[2*index];
					array[2*index] = temp;
					removeSwap(2*index);
				}
				else if(priority(array[2*index + 1], array[2*index]) > 0){
					temp=array[index];
					array[index] = array[2*index + 1];
					array[2*index + 1] = temp;
					removeSwap(2*index + 1);
				}
				else{
					//if the comparing value is the same, swapping is not needed.
					return; 
				}
			}
		}
	}

	/**
	 * add() method.
	 * @param data the data to add
	 * This method adds the element in the heap.
	 * It does the resize if needed.
	 */
	
	public void add(T data) {
		//If the array is full, resize.
		if(array.length== size()+1){
			resize();
		}
		
		//Add the first element in the index 1.
		if(isEmpty()){
			array[1] = data;
			size++;
		}
		else{
			array[size+1] = data;
			size++;
			addSwap(size);
		}
	}
	
	/**
	 * addSwap() method.
	 * @param index
	 * This method does the swapping operation recursively.
	 */
	
	private void addSwap(int index){
		T temp;
		if(priority(array[index], array[divideByTwo(index)]) > 0){
			temp=array[index];
			array[index] = array[divideByTwo(index)];
			array[divideByTwo(index)] = temp;
			addSwap(divideByTwo(index));
		}
		else{
			return;
		}
	}

	/**
	 * addAll() method.
	 * @param Collection<T> 
	 * This method adds all the elements in a collection.
	 */
	
	public void addAll(Collection<T> elements) {
		
		Iterator<T> it = elements.iterator();
		while(it.hasNext()){
			add(it.next());
		}
	}
	
	/**
	 * divideByTwo() method.
	 * @param i an integer to add.
	 * @return int 
	 * Dividing 1 by 2 should give us 1, otherwise do the standard integer division.
	 */
	
	private int divideByTwo(int i){
		if(i==1){
			return 1;
		}
		else{
			return i/2;
		}
	}
	
	/**
	 * resize() method.
	 * This method makes a new array that is twice bigger than
	 * the original one.
	 */
	
	private void resize(){
		T[] newArray = (T[]) new Comparable[array.length*2];
		
		for(int i=0; i<size()+1; i++){
			newArray[i] = array[i];
		}
		
		array = newArray;
	}

	// do not modify methods below this point, they are for grading purposes

	@Override
	public T[] getArray() {
		return array;
	}

	@Override
	public void setArray(T[] array) {
		this.array = array;
	}

	@Override
	public void setSize(int size) {
		this.size = size;
	}
}
